package Prac;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class P11_27 {

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new LinkedList<>();
        if(root==null){
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            List<Integer> list = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                TreeNode top = queue.poll();
                int val = top.val;
                if(top.left!=null){
                    queue.offer(top.left);
                }
                if(top.right!=null){
                    queue.offer(top.right);
                }
                list.add(val);
            }
            ret.add(list);
        }
        return ret;
    }

    public boolean isSymmetric(TreeNode root) {
        return isMirror(root.left,root.right);
    }

    /**
     * 传入两根节点,判断两个树是否为对称
     * @param t1
     * @param t2
     * @return
     */
    private boolean isMirror(TreeNode t1, TreeNode t2) {//参数保证位置对称
        //函数内部保证值相等
        //对称的位置值相等则树对称
        if(t1==null&&t2==null){
            return true;
        }
        if(t1==null||t2==null){
            return false;
        }
        if(t1.val!=t2.val){
            return false;
        }
        return isMirror(t1.left,t2.right)&&isMirror(t1.right,t2.left);
    }

    public boolean isBalanced(TreeNode root) {
        if(root==null||(root.left==null&&root.right==null)){
            return true;
        }
        int rightHeight = height(root.right);
        int leftHeight = height(root.left);
        int abs = Math.abs(rightHeight-leftHeight);
        if(abs>1){
            return false;
        }
        return isBalanced(root.left)&&isBalanced(root.right);
    }

    private int height(TreeNode root) {
        if(root==null){
            return 0;
        }
        return 1+Math.max(height(root.left),height(root.right));
    }

    public TreeNode invertTree(TreeNode root) {
        if(root==null||(root.left==null&&root.right==null)){
            return root;
        }
        root.left = invertTree(root.left);
        root.right = invertTree(root.right);
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        return root;
    }

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root==null&&subRoot==null){
            return true;
        }
        if(root==null||subRoot==null){
            return false;
        }
        if(isSameTree(root,subRoot)){
            return true;
        }
        return isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot);
    }
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q==null){
            return true;
        }
        if((p!=null&&q==null)||(p==null&&q!=null)){
            return false;
        }
        return p.val==q.val&&isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
}
